The present invention relates to data processors, and more particularly, to a data processor having a pipeline-parallel structure to rapidly solve optimization problems.
Dynamic programming provides a sequential decision-making method of solving optimization problems. Plotting the path of a military tank from one position on a battlefield to another position while considering the terrain, amount of concealment, available roads, enemy movement, fuel consumption, etc. is one practical application of dynamic programming. Dynamic programming converts a comparison of the many overall choices to select the optimum choice into a sequential comparison of much simplier intermediate optimization problems. When plotting tank movement, the space (state space) through which the tank can travel is divided into a plurality of space areas or cells. The optimum transition from one cell to each of the adjacent cells closer to the final position is then calculated. The optimum path may be determined by all, or only a part of the factors which can be considered, depending upon choices made by a human operator or director.
The candidate optimum transitions of the tank from each and every one of the cells in the state space between the starting and ending points are compared, and these optimum transitions are used to calculate the overall optimum path between starting and ending points. It is often more efficient to start calculations at the cell containing the ending point and perform the dynamic programming calculations in reverse toward the starting point.
In order for dynamic programming to be useful in solving problems in real-time, solutions must be obtained very rapidly. For example, when plotting an optimum path for a military tank, if a solution is obtained at a slow rate the tank could change its position so fast that the solution would not be optimum by the time a first portion of the solution is obtained.
One method of rapidly obtaining an optimum path is to assign values to the cost of moving outward from the end-point cell in each direction to adjacent cells and use these values to calculate the lowest cost to reach a starting-point cell. The cost of moving from the end-point cell to each of the 8 adjacent cells is simultaneously calculated and the lowest cell is selected by a comparator circuit having 8 inputs. This process is repeated until the desired starting-point cell is reached.